{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "# 冒泡排序\n",
    "\"\"\"\n",
    "时间复杂度：O(n^2)\n",
    "空间复杂度：O(1)\n",
    "稳定性：稳定\n",
    "\"\"\"\n",
    "def bubble_sort(array):\n",
    "    for i in range(len(array)):\n",
    "        for j in range(i, len(array)):\n",
    "            if array[i] > array[j]:\n",
    "                array[i], array[j] = array[j], array[i]\n",
    "    return array\n",
    "\n",
    "# 快速排序\n",
    "\"\"\"\n",
    "时间复杂度：O(nlog₂n)\n",
    "空间复杂度：O(nlog₂n)\n",
    "稳定性：不稳定\n",
    "\"\"\"\n",
    "def quick_sort(array):\n",
    "    def recursive(begin, end):\n",
    "        if begin > end:\n",
    "            return\n",
    "        l, r = begin, end\n",
    "        pivot = array[l]\n",
    "        while l < r:\n",
    "            while l < r and array[r] > pivot:\n",
    "                r -= 1\n",
    "            while l < r and array[l] <= pivot:\n",
    "                l += 1\n",
    "            array[l], array[r] = array[r], array[l]\n",
    "        array[l], array[begin] = pivot, array[l]\n",
    "        recursive(begin, l - 1)\n",
    "        recursive(r + 1, end)\n",
    "    recursive(0, len(array) - 1)\n",
    "    return array\n",
    "\n",
    "# 直接插入排序\n",
    "\"\"\"\n",
    "时间复杂度：O(n²)\n",
    "空间复杂度：O(1)\n",
    "稳定性：稳定\n",
    "\"\"\"\n",
    "def insert_sort(array):\n",
    "    for i in range(len(array)):\n",
    "        for j in range(i):\n",
    "            if array[i] < array[j]:\n",
    "                array.insert(j, array.pop(i))\n",
    "                break\n",
    "    return array\n",
    "\n",
    "# 希尔排序\n",
    "\"\"\"\n",
    "时间复杂度：O(n)\n",
    "空间复杂度：O(n√n)\n",
    "稳定性：不稳定\n",
    "\"\"\"\n",
    "def shell_sort(array):\n",
    "    gap = len(array)\n",
    "    while gap > 1:\n",
    "        gap = gap // 2\n",
    "        for i in range(gap, len(array)):\n",
    "            for j in range(i % gap, i, gap):\n",
    "                if array[i] < array[j]:\n",
    "                    array[i], array[j] = array[j], array[i]\n",
    "    return array\n",
    "\n",
    "# 简单选择排序\n",
    "\"\"\"\n",
    "时间复杂度：O(n²)\n",
    "空间复杂度：O(1)\n",
    "稳定性：不稳定\n",
    "\"\"\"\n",
    "def select_sort(array):\n",
    "    for i in range(len(array)):\n",
    "        x = i  # min index\n",
    "        for j in range(i, len(array)):\n",
    "            if array[j] < array[x]:\n",
    "                x = j\n",
    "        array[i], array[x] = array[x], array[i]\n",
    "    return array\n",
    "\n",
    "# 堆排序\n",
    "\"\"\"\n",
    "时间复杂度：O(nlog₂n)\n",
    "空间复杂度：O(1)\n",
    "稳定性：不稳定\n",
    "\"\"\"\n",
    "def heap_sort(array):\n",
    "    def heap_adjust(parent):\n",
    "        child = 2 * parent + 1  # left child\n",
    "        while child < len(heap):\n",
    "            if child + 1 < len(heap):\n",
    "                if heap[child + 1] > heap[child]:\n",
    "                    child += 1  # right child\n",
    "            if heap[parent] >= heap[child]:\n",
    "                break\n",
    "            heap[parent], heap[child] = \\\n",
    "                heap[child], heap[parent]\n",
    "            parent, child = child, 2 * child + 1\n",
    "\n",
    "    heap, array = array.copy(), []\n",
    "    for i in range(len(heap) // 2, -1, -1):\n",
    "        heap_adjust(i)\n",
    "    while len(heap) != 0:\n",
    "        heap[0], heap[-1] = heap[-1], heap[0]\n",
    "        array.insert(0, heap.pop())\n",
    "        heap_adjust(0)\n",
    "    return array\n",
    "\n",
    "# 归并排序\n",
    "\"\"\"\n",
    "时间复杂度：O(nlog₂n)\n",
    "空间复杂度：O(1)\n",
    "稳定性：稳定\n",
    "\"\"\"\n",
    "def merge_sort(array):\n",
    "    def merge_arr(arr_l, arr_r):\n",
    "        array = []\n",
    "        while len(arr_l) and len(arr_r):\n",
    "            if arr_l[0] <= arr_r[0]:\n",
    "                array.append(arr_l.pop(0))\n",
    "            elif arr_l[0] > arr_r[0]:\n",
    "                array.append(arr_r.pop(0))\n",
    "        if len(arr_l) != 0:\n",
    "            array += arr_l\n",
    "        elif len(arr_r) != 0:\n",
    "            array += arr_r\n",
    "        return array\n",
    "\n",
    "    def recursive(array):\n",
    "        if len(array) == 1:\n",
    "            return array\n",
    "        mid = len(array) // 2\n",
    "        arr_l = recursive(array[:mid])\n",
    "        arr_r = recursive(array[mid:])\n",
    "        return merge_arr(arr_l, arr_r)\n",
    "\n",
    "    return recursive(array)\n",
    "\n",
    "# 基数排序\n",
    "\"\"\"\n",
    "时间复杂度：O(d(r+n))\n",
    "空间复杂度：O(rd+n)\n",
    "稳定性：稳定\n",
    "\"\"\"\n",
    "def radix_sort(array):\n",
    "    bucket, digit = [[]], 0\n",
    "    while len(bucket[0]) != len(array):\n",
    "        bucket = [[], [], [], [], [], [], [], [], [], []]\n",
    "        for i in range(len(array)):\n",
    "            num = (array[i] // 10 ** digit) % 10\n",
    "            bucket[num].append(array[i])\n",
    "        array.clear()\n",
    "        for i in range(len(bucket)):\n",
    "            array += bucket[i]\n",
    "        digit += 1\n",
    "    return array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "第 1 种排序算法平均用时为： 0.34481972455978394\n",
      "第 2 种排序算法平均用时为： 0.2597648620605469\n",
      "第 3 种排序算法平均用时为： 0.20066148042678833\n",
      "第 4 种排序算法平均用时为： 0.32751872539520266\n",
      "第 5 种排序算法平均用时为： 0.20161153078079225\n",
      "第 6 种排序算法平均用时为： 0.018401062488555907\n",
      "第 7 种排序算法平均用时为： 0.010600614547729491\n",
      "第 8 种排序算法平均用时为： 0.010600602626800537\n"
     ]
    }
   ],
   "source": [
    "# 排序速度比较\n",
    "import os\n",
    "import random\n",
    "from json import dumps, loads\n",
    "from _datetime import datetime\n",
    "\n",
    "# 生成随机数文件\n",
    "def dump_random_array(file='numbers.json', size=10 ** 3):\n",
    "    fo = open(file, 'w', 1024)\n",
    "    numlst = list()\n",
    "    for i in range(size):\n",
    "        c = random.randint(0,1000000)\n",
    "        if len(numlst)>0:\n",
    "            for j in range(len(numlst)):\n",
    "                if numlst[j] == c:\n",
    "                    numlst.append(c + 1234)\n",
    "                    break\n",
    "                elif j == len(numlst)-1:\n",
    "                    numlst.append(c)\n",
    "                else:\n",
    "                    continue\n",
    "        else:\n",
    "            numlst.append(c)\n",
    "    fo.write(dumps(numlst))\n",
    "    fo.close()\n",
    "\n",
    "\n",
    "# 加载随机数列表\n",
    "def load_random_array(file='numbers.json'):\n",
    "    fo = open(file, 'r', 1024)\n",
    "    try:\n",
    "        numlst = fo.read()\n",
    "    finally:\n",
    "        fo.close()\n",
    "        #os.remove(file)\n",
    "    return loads(numlst)\n",
    "\n",
    "# 显示函数执行时间\n",
    "def exectime(func, *args, **kwargs):\n",
    "    begin = time.time()\n",
    "    res = func(*args, **kwargs)\n",
    "    end = time.time()\n",
    "    inter = end - begin\n",
    "    return inter\n",
    "\n",
    "\"\"\"\n",
    "a = [99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,\n",
    "    79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,\n",
    "    59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,\n",
    "    39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,\n",
    "    19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0]\n",
    "time1=time.time()\n",
    "print(merge_sort(a))\n",
    "time2=time.time()\n",
    "print(\"用时：\",time2-time1)\n",
    "\"\"\"\n",
    "\n",
    "# 定义不同排序函数名数组\n",
    "s = [bubble_sort,\n",
    "     quick_sort,\n",
    "     insert_sort,\n",
    "     shell_sort,\n",
    "     select_sort,\n",
    "     heap_sort,\n",
    "     merge_sort,\n",
    "     radix_sort]\n",
    "# 随机生成20组不同的待排序数组\n",
    "nk = []\n",
    "for k in range(20):\n",
    "    dump_random_array(file='numbers.json', size=1000)\n",
    "    nk.append(load_random_array(file='numbers.json'))\n",
    "# 分别以不同排序算法对20组数据进行排序，并计算排序用时\n",
    "for i in range(len(s)):\n",
    "    t = 0\n",
    "    at = 0\n",
    "    for j in range(len(nk)):\n",
    "        t = t + exectime(s[i], nk[j])\n",
    "    at = t / len(nk)\n",
    "    print(\"第\",i+1,\"种排序算法平均用时为：\",at)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
